package com.cyx;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * @author 陈裕星
 * @version 1.0
 * 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，
 * 找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * 输入: candidates = [2,3,5], target = 8
 * 输出: [[2,2,2,2],[2,3,3],[3,5]]
 */
public class 组合总和 {
    static List<List<Integer>> res = new ArrayList<>();
    static List<Integer> tmp = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] candidates = new int[n];
        for (int i = 0; i < n; i++) {
            candidates[i] = sc.nextInt();
        }
        int target = sc.nextInt();

        //排序，方便操作
        Arrays.sort(candidates);

        backtrack(candidates,0,target);
        System.out.println(res.toString());
    }

    static void backtrack(int[] candidates,int start, int target){
        if(target == 0){
            res.add(new ArrayList<>(tmp));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            //剪枝
            if( candidates[i] >  target) break;

            tmp.add(candidates[i]);
            backtrack(candidates,i,target-candidates[i]);
            //回溯
            tmp.remove(tmp.size()-1);
        }
    }
}
